#include <iostream>
#include <stack>

class BitNode
{
  public:
    BitNode(){}
    explicit BitNode(int _data) : data(_data), lchild(nullptr), rchild(nullptr) {}
    ~BitNode(){}
  public:
    int data;
    BitNode *lchild, *rchild;
};

void visit(int data)
{
  std::cout << data << std::endl;
}

void inOrder(const BitNode* tree)
{
  if (tree != nullptr) {
    inOrder(tree->lchild);
    visit(tree->data);
    inOrder(tree->rchild);
  }
}

BitNode* insertNode(BitNode* tree, int data)
{
  if (tree == nullptr) {
    return new BitNode(data);
  }

  if (data < tree->data) {
    tree->lchild = insertNode(tree->lchild, data);
  }
  if (data > tree->data) {
    tree->rchild = insertNode(tree->rchild, data);
  }
  return tree;
}

BitNode* delRoot(BitNode* tree)
{
  if (tree == nullptr) {
    return nullptr;
  }

  BitNode* new_tree = nullptr;
  if (tree->lchild == nullptr) {
    new_tree = tree->rchild;
  } else if (tree->rchild == nullptr) {
    new_tree = tree->lchild;
  } else {
    BitNode* rmin_fd = tree;
    BitNode* rmin = tree->rchild;
    while (rmin->lchild != nullptr) {
      rmin_fd = rmin;
      rmin = rmin->lchild;
    }

    rmin->lchild = tree->lchild;
    if (rmin != tree->rchild) {
      rmin_fd->lchild = rmin->rchild;
      rmin->rchild = tree->rchild;
    }
    new_tree = rmin;
  }

  free(tree);
  return new_tree;
}

BitNode* delNode(BitNode* tree, int data)
{
  if (tree == nullptr) {
    return nullptr;
  }

  if (data == tree->data) {
    return delRoot(tree);
  }

  if (data < tree->data) {
    tree->lchild = delNode(tree->lchild, data);
  }
  if (data > tree->data) {
    tree->rchild = delNode(tree->rchild, data);
  }
  return tree;
}

const BitNode* searchNode(const BitNode* tree, int data)
{
  if (tree == nullptr) {
    return nullptr;
  }

  if (tree->data == data) {
    return tree;
  } else if (data < tree->data ) {
    return searchNode(tree->lchild, data);
  } else {
    return searchNode(tree->rchild, data);
  }
}

int main()
{
  BitNode* tree = nullptr;
  tree = insertNode(tree, 9);
  tree = insertNode(tree, 12);
  tree = insertNode(tree, 7);
  tree = insertNode(tree, 8);
  tree = insertNode(tree, 15);

  inOrder(tree);
  auto p_node = searchNode(tree, 15);
  if (p_node != nullptr) {
    visit(p_node->data);
  }

  std::cout << std::endl;
  tree = delNode(tree, 7);
  inOrder(tree);
  return 0;
}

